package org.example.myleet.p872;

import org.example.myleet.Utils.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 1 ms
 * DFS，找到叶子就往结果里面叠加，最后比较输出的叶子节点顺序
 */
public class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = getLeavesDfs(root1);
        List<Integer> leaves2 = getLeavesDfs(root2);
        return leaves1.equals(leaves2);
    }

    private List<Integer> getLeavesDfs(TreeNode root) {
        List<Integer> leaves = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.left == null && cur.right == null) {
                leaves.add(cur.val);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return leaves;
    }
}
